public class 删除链表的倒数第N个结点 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 引入头节点, 可以避免处理边界情况
        ListNode t = new ListNode();
        t.next = head;
        ListNode cur = t; // 可以到倒数第 n 个节点
        // 提前处理
        ListNode fast = t;
        while (n-- > 0) {
            fast = fast.next;
        }
        // 找到前一个节点
        ListNode pre = null;
        while (fast != null) {
            pre = cur;
            cur = cur.next;
            fast = fast.next;
        }
        pre.next = cur.next;
        return t.next;
    }
}
